package org.example.leetCode;

import org.example.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 94. 二叉树的中序遍历
 * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 */
public class Code94 {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        dfs(list,root);
        return list;
    }

    private void dfs(ArrayList<Integer> list, TreeNode root) {
        if(root==null)
            return;
        dfs(list,root.left);
        list.add(root.val);
        dfs(list,root.right);
    }

    public List<Integer> df(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) return list;

        TreeNode[] stack = new TreeNode[100];
        int top = -1;
        TreeNode current = root;

        // 标准的中序遍历迭代实现
        while (top >= 0 || current != null) {
            // 一直向左走到底，将路径上的节点都入栈
            if (current != null) {
                stack[++top] = current;
                current = current.left;
            } else {
                // 弹出栈顶节点并访问
                current = stack[top--];
                list.add(current.val);
                // 转向右子树
                current = current.right;
            }
        }
        return list;
    }
}
